package com.acwing.lc.part1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author rkc
 * @date 2022/9/11 15:15
 */
public class LC30串联所有单词的子串 {

    private Map<String, Integer> map = new HashMap<>();

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        if (words.length == 0) return ans;
        int n = s.length(), m = words.length, w = words[0].length();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < w; i++) {
            Map<String, Integer> wd = new HashMap<>();
            int cnt = 0;
            for (int j = i; j + w <= n; j += w) {
                if (j >= i + m * w) {
                    String word = s.substring(j - m * w, j - m * w + w);
                    wd.put(word, wd.getOrDefault(word, 0) - 1);
                    if (wd.get(word) < map.getOrDefault(word, 0)) cnt--;
                }
                String word = s.substring(j, j + w);
                wd.put(word, wd.getOrDefault(word, 0) + 1);
                if (wd.get(word) <= map.getOrDefault(word, 0)) cnt++;
                if (cnt == m) ans.add(j - (m - 1) * w);
            }
        }
        return ans;
    }
}
